from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        return self._search_trans(nums, target)

    def _search_trans(self, nums, target, s=0):
        # print(nums)
        if nums[0] == target:
            return s + 0
        if len(nums) == 1:
            return -1
        mid = len(nums) // 2
        if nums[mid] == target:
            return s+mid
        if nums[mid] < nums[0]:  # 说明左侧是trans,右侧升序
            if nums[mid] < target < nums[0]: # 如在升序的范围中，在升序列表中找target
                return self._search_arise(nums[mid:], target, s+mid)
            else:
                return self._search_trans(nums[:mid], target, s)
        else:  # 左侧升序，
            if nums[0] < target < nums[mid]:
                return self._search_arise(nums[:mid], target, s)
            else:
                return self._search_trans(nums[mid:], target, s+mid)

    def _search_arise(self, nums, target, s=0):
        # print(nums)
        if len(nums) == 0:
            return -1
        mid = len(nums) // 2
        if nums[mid] == target:
            return mid + s
        if len(nums) == 1:
            return -1
        if nums[mid] < target:
            return self._search_arise(nums[mid:], target, s+mid)
        else:
            return self._search_arise(nums[:mid], target, s)



if __name__ == "__main__":
    s = Solution()
    print(s.search(nums = [4,5,6,7,0,1,2], target = 0))
    print(s.search(nums = [4,5,6,7,0,1,2], target = 3))
    print(s.search(nums = [4,5,6,7,0,1,2], target = 6))
